/*
        This file is part of cpp-ethereum.
        cpp-ethereum is free software: you can redistribute it and/or modify
        it under the terms of the GNU General Public License as published by
        the Free Software Foundation, either version 3 of the License, or
        (at your option) any later version.
        cpp-ethereum is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.
        You should have received a copy of the GNU General Public License
        along with cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
*/
/** @file TrieDB.h
 * @author Gav Wood <i@gavwood.com>
 * @date 2014
 */

#ifndef __TRIEDB_H__
#define __TRIEDB_H__

#include <map>
#include <memory>

#include "TrieCommon.h"
#include "libUtils/Logger.h"
#include "depends/common/Exceptions.h"
#include "depends/common/SHA3.h"

namespace dev {
struct InvalidTrie : virtual dev::Exception {};

enum class Verification { Skip, Normal };

/**
 * @brief Merkle Patricia Tree "Trie": a modifed base-16 Radix tree.
 * This version uses a database backend.
 * Usage:
 * @code
 * GenericTrieDB<MyDB> t(&myDB);
 * assert(t.isNull());
 * t.init();
 * assert(t.isEmpty());
 * t.insert(x, y);
 * assert(t.at(x) == y.toString());
 * t.remove(x);
 * assert(t.isEmpty());
 * @endcode
 */
template <class _DB>
class GenericTrieDB {
 public:
  using DB = _DB;

  explicit GenericTrieDB(DB* _db = nullptr) : m_db(_db) {}

  GenericTrieDB(DB* _db, h256 const& _root,
                Verification _v = Verification::Normal) {
    open(_db, _root, _v);
  }

  ~GenericTrieDB() {}

  void open(DB* _db) { m_db = _db; }

  void open(DB* _db, h256 const& _root,
            Verification _v = Verification::Normal) {
    m_db = _db;
    setRoot(_root, _v);
  }

  void init() const {
    setRoot(forceInsertNode(&RLPNull));

    ZIL_FATAL_ASSERT(node(m_root).size() != 0);
  }

  void setRoot(h256 const& _root,
               Verification _v = Verification::Normal) const {
    m_root = _root;
    if (_v == Verification::Normal) {
      if (m_root == EmptyTrie && !m_db->exists(m_root)) {
        init();
      }
    }
    /*std::cout << "Setting root to " << _root << " (patched to " << m_root <<
     * ")" << std::endl;*/
#if ETH_DEBUG
    if (_v == Verification::Normal)
#endif
      if (!node(m_root).size()) {
        BOOST_THROW_EXCEPTION(RootNotFound());
      }
  }

  /// True if the trie is uninitialised (i.e. that the DB doesn't contain the
  /// root node).
  bool isNull() const { return !node(m_root).size(); }
  /// True if the trie is initialised but empty (i.e. that the DB contains the
  /// root node which is empty).
  bool isEmpty() const { return m_root == EmptyTrie && node(m_root).size(); }

  h256 const& root() const {
    if (node(m_root).empty()) {
      BOOST_THROW_EXCEPTION(BadRoot(m_root));
      /*std::cout << "Returning root as " << ret << " (really " << m_root << ")"
       * << std::endl;*/
    }
    return m_root;
  }  // patch the root in the case of the empty trie. TODO: handle this
     // properly.

  std::string at(zbytes const& _key) const { return at(&_key); }

  std::string at(zbytesConstRef _key) const;

  void insert(zbytes const& _key, zbytes const& _value) {
    insert(&_key, &_value);
  }

  void insert(zbytesConstRef _key, zbytes const& _value) {
    insert(_key, &_value);
  }

  void insert(zbytes const& _key, zbytesConstRef _value) {
    insert(&_key, _value);
  }

  void insert(zbytesConstRef _key, zbytesConstRef _value);

  void remove(zbytes const& _key) { remove(&_key); }
  void remove(zbytesConstRef _key);

  bool contains(zbytes const& _key) const { return contains(&_key); }
  bool contains(zbytesConstRef _key) const { return !at(_key).empty(); }

  std::string getProof(zbytes const& _key, std::set<std::string>& nodes) const {
    return getProof(&_key, nodes);
  }

  std::string getProof(zbytesConstRef _key, std::set<std::string>& nodes) const;

  class iterator {
   public:
    using value_type = std::pair<zbytesConstRef, zbytesConstRef>;

    iterator() {}
    explicit iterator(GenericTrieDB const* _db);
    iterator(GenericTrieDB const* _db, zbytesConstRef _key);

    iterator& operator++() {
      next();
      return *this;
    }

    value_type operator*() const { return at(); }
    value_type operator->() const { return at(); }

    bool operator==(iterator const& _c) const { return _c.m_trail == m_trail; }
    bool operator!=(iterator const& _c) const { return _c.m_trail != m_trail; }

    value_type at() const;

   private:
    void next();
    void next(NibbleSlice _key);

    struct Node {
      std::string rlp;
      std::string key;  // as hexPrefixEncoding.
      zbyte child;      // 255 -> entering, 16 -> actually at the node, 17 ->
                        // exiting, 0-15 -> actual children.

      // 255 -> 16 -> 0 -> 1 -> ... -> 15 -> 17

      void setChild(unsigned _i) { child = _i; }
      void setFirstChild() { child = 16; }
      void incrementChild() {
        child = child == 16 ? 0 : child == 15 ? 17 : (child + 1);
      }

      bool operator==(Node const& _c) const {
        return rlp == _c.rlp && key == _c.key && child == _c.child;
      }
      bool operator!=(Node const& _c) const { return !operator==(_c); }
    };

   protected:
    std::vector<Node> m_trail;
    GenericTrieDB<DB> const* m_that;
  };

  iterator begin() const { return iterator(this); }
  iterator end() const { return iterator(); }

  iterator lower_bound(zbytesConstRef _key) const {
    return iterator(this, _key);
  }

  /// Used for debugging, scans the whole trie.
  void descendKey(h256 const& _k, h256Hash& _keyMask, bool _wasExt,
                  std::ostream* _out, int _indent = 0) const {
    _keyMask.erase(_k);
    if (_k == m_root && _k == EmptyTrie)  // root allowed to be empty
      return;
    descendList(RLP(node(_k)), _keyMask, _wasExt, _out,
                _indent);  // if not, it must be a list
  }

  /// Used for debugging, scans the whole trie.
  void descendEntry(RLP const& _r, h256Hash& _keyMask, bool _wasExt,
                    std::ostream* _out, int _indent) const {
    if (_r.isData() && _r.size() == 32)
      descendKey(_r.toHash<h256>(), _keyMask, _wasExt, _out, _indent);
    else if (_r.isList())
      descendList(_r, _keyMask, _wasExt, _out, _indent);
    else
      BOOST_THROW_EXCEPTION(InvalidTrie());
  }

  /// Used for debugging, scans the whole trie.
  void descendList(RLP const& _r, h256Hash& _keyMask, bool _wasExt,
                   std::ostream* _out, int _indent) const {
    if (_r.isList() && _r.itemCount() == 2 && (!_wasExt || _out)) {
      if (_out)
        (*_out) << std::string(_indent * 2, ' ') << (_wasExt ? "!2 " : "2  ")
                << sha3(_r.data()) << ": " << _r << "\n";
      if (!isLeaf(_r))  // don't go down leaves
        descendEntry(_r[1], _keyMask, true, _out, _indent + 1);
    } else if (_r.isList() && _r.itemCount() == 17) {
      if (_out)
        (*_out) << std::string(_indent * 2, ' ') << "17 " << sha3(_r.data())
                << ": " << _r << "\n";
      for (unsigned i = 0; i < 16; ++i)
        if (!_r[i].isEmpty())  // 16 branches are allowed to be empty
          descendEntry(_r[i], _keyMask, false, _out, _indent + 1);
    } else
      BOOST_THROW_EXCEPTION(InvalidTrie());
  }

  /// Used for debugging, scans the whole trie.
  h256Hash leftOvers(std::ostream* _out = nullptr) const {
    h256Hash k = m_db->keys();
    descendKey(m_root, k, false, _out);
    return k;
  }

  /// Used for debugging, scans the whole trie.
  void debugStructure(std::ostream& _out) const { leftOvers(&_out); }

  /// Used for debugging, scans the whole trie.
  /// @param _requireNoLeftOvers if true, requires that all keys are reachable.
  bool check(bool _requireNoLeftOvers) const {
    try {
      return leftOvers().empty() || !_requireNoLeftOvers;
    } catch (...) {
      return false;
    }
  }

  /// Get the underlying database.
  /// @warning This can be used to bypass the trie code. Don't use these unless
  /// you *really* know what you're doing.
  DB const* db() const { return m_db; }
  DB* db() { return m_db; }

 private:
  RLPStream& streamNode(RLPStream& _s, zbytes const& _b);

  std::string atAux(RLP const& _here, NibbleSlice _key) const;

  std::string getProof(RLP const& _here, NibbleSlice _key,
                       std::set<std::string>& nodes) const;

  void mergeAtAux(RLPStream& _out, RLP const& _replace, NibbleSlice _key,
                  zbytesConstRef _value);
  zbytes mergeAt(RLP const& _replace, NibbleSlice _k, zbytesConstRef _v,
                 bool _inLine = false);
  zbytes mergeAt(RLP const& _replace, h256 const& _replaceHash, NibbleSlice _k,
                 zbytesConstRef _v, bool _inLine = false);

  bool deleteAtAux(RLPStream& _out, RLP const& _replace, NibbleSlice _key);
  zbytes deleteAt(RLP const& _replace, NibbleSlice _k);

  // in: null (DEL)  -- OR --  [_k, V] (DEL)
  // out: [_k, _s]
  // -- OR --
  // in: [V0, ..., V15, S16] (DEL)  AND  _k == {}
  // out: [V0, ..., V15, _s]
  zbytes place(RLP const& _orig, NibbleSlice _k, zbytesConstRef _s);

  // in: [K, S] (DEL)
  // out: null
  // -- OR --
  // in: [V0, ..., V15, S] (DEL)
  // out: [V0, ..., V15, null]
  zbytes remove(RLP const& _orig);

  // in: [K1 & K2, V] (DEL) : nibbles(K1) == _s, 0 < _s <= nibbles(K1 & K2)
  // out: [K1, H] ; [K2, V] => H (INS)  (being  [K1, [K2, V]]  if necessary)
  zbytes cleve(RLP const& _orig, unsigned _s);

  // in: [K1, H] (DEL) ; H <= [K2, V] (DEL)  (being  [K1, [K2, V]] (DEL)  if
  // necessary) out: [K1 & K2, V]
  zbytes graft(RLP const& _orig);

  // in: [V0, ... V15, S] (DEL)
  // out1: [k{i}, Vi]    where i < 16
  // out2: [k{}, S]      where i == 16
  zbytes merge(RLP const& _orig, zbyte _i);

  // in: [k{}, S] (DEL)
  // out: [null ** 16, S]
  // -- OR --
  // in: [k{i}, N] (DEL)
  // out: [null ** i, N, null ** (16 - i)]
  // -- OR --
  // in: [k{i}K, V] (DEL)
  // out: [null ** i, H, null ** (16 - i)] ; [K, V] => H (INS)  (being [null **
  // i, [K, V], null ** (16 - i)]  if necessary)
  zbytes branch(RLP const& _orig);

  bool isTwoItemNode(RLP const& _n) const;
  std::string deref(RLP const& _n) const;

  std::string node(h256 const& _h) const { return m_db->lookup(_h); }

  // These are low-level node insertion functions that just go straight through
  // into the DB.
  h256 forceInsertNode(zbytesConstRef _v) const {
    auto h = sha3(_v);
    forceInsertNode(h, _v);
    return h;
  }
  void forceInsertNode(h256 const& _h, zbytesConstRef _v) const {
    m_db->insert(_h, _v);
  }
  void forceKillNode(h256 const& _h) { m_db->kill(_h); }

  // This are semantically-aware node insertion functions that only kills when
  // the node's data is < 32 bytes. It can safely be used when pruning the trie
  // but won't work correctly for the special case of the root (which is always
  // looked up via a hash). In that case, use forceKillNode().
  void killNode(RLP const& _d) {
    if (_d.data().size() >= 32) forceKillNode(sha3(_d.data()));
  }
  void killNode(RLP const& _d, h256 const& _h) {
    if (_d.data().size() >= 32) forceKillNode(_h);
  }

  mutable h256 m_root;
  DB* m_db = nullptr;
};

template <class DB>
std::ostream& operator<<(std::ostream& _out, GenericTrieDB<DB> const& _db) {
  for (auto const& i : _db)
    _out << escaped(i.first.toString(), false) << ": "
         << escaped(i.second.toString(), false) << std::endl;
  return _out;
}

/**
 * Different view on a GenericTrieDB that can use different key types.
 */
template <class Generic, class _KeyType>
class SpecificTrieDB : public Generic {
 public:
  using DB = typename Generic::DB;
  using KeyType = _KeyType;

  SpecificTrieDB(DB* _db = nullptr) : Generic(_db) {}
  SpecificTrieDB(DB* _db, h256 _root, Verification _v = Verification::Normal)
      : Generic(_db, _root, _v) {}

  std::string operator[](KeyType _k) const { return at(_k); }

  bool contains(KeyType _k) const {
    return Generic::contains(
        zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)));
  }

  std::string at(KeyType _k) const {
    zbytesConstRef((zbyte const*)&_k, sizeof(KeyType));

    return Generic::at(zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)));
  }

  std::string getProof(KeyType _k, std::set<std::string>& nodes) const {
    zbytesConstRef((zbyte const*)&_k, sizeof(KeyType));

    return Generic::getProof(zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)),
                             nodes);
  }

  void insert(KeyType _k, zbytesConstRef _value) {
    //            LOG_GENERAL(INFO, "Inserting to SpecificTrieDB Key : Value = "
    //            << _k << " : " << _value);
    Generic::insert(zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)), _value);
  }
  void insert(KeyType _k, zbytes const& _value) {
    insert(_k, zbytesConstRef(&_value));
  }
  void remove(KeyType _k) {
    Generic::remove(zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)));
  }

  class iterator : public Generic::iterator {
   public:
    using Super = typename Generic::iterator;
    using value_type = std::pair<KeyType, zbytesConstRef>;

    iterator() {}
    iterator(Generic const* _db) : Super(_db) {}
    iterator(Generic const* _db, zbytesConstRef _k) : Super(_db, _k) {}

    value_type operator*() const { return at(); }
    value_type operator->() const { return at(); }

    value_type at() const;
  };

  iterator begin() const { return this; }
  iterator end() const { return iterator(); }
  iterator lower_bound(KeyType _k) const {
    return iterator(this, zbytesConstRef((zbyte const*)&_k, sizeof(KeyType)));
  }
};

template <class Generic, class KeyType>
std::ostream& operator<<(std::ostream& _out,
                         SpecificTrieDB<Generic, KeyType> const& _db) {
  for (auto const& i : _db)
    _out << i.first << ": " << escaped(i.second.toString(), false) << std::endl;
  return _out;
}

template <class _DB>
class HashedGenericTrieDB : private SpecificTrieDB<GenericTrieDB<_DB>, h256> {
  using Super = SpecificTrieDB<GenericTrieDB<_DB>, h256>;

 public:
  using DB = _DB;

  HashedGenericTrieDB(DB* _db = nullptr) : Super(_db) {}
  HashedGenericTrieDB(DB* _db, h256 _root,
                      Verification _v = Verification::Normal)
      : Super(_db, _root, _v) {}

  using Super::init;
  using Super::open;
  using Super::setRoot;

  /// True if the trie is uninitialised (i.e. that the DB doesn't contain the
  /// root node).
  using Super::isNull;
  /// True if the trie is initialised but empty (i.e. that the DB contains the
  /// root node which is empty).
  using Super::isEmpty;

  using Super::db;
  using Super::root;

  using Super::check;
  using Super::debugStructure;
  using Super::leftOvers;

  std::string at(zbytesConstRef _key) const { return Super::at(sha3(_key)); }
  bool contains(zbytesConstRef _key) const {
    return Super::contains(sha3(_key));
  }
  void insert(zbytesConstRef _key, zbytesConstRef _value) {
    Super::insert(sha3(_key), _value);
  }
  void remove(zbytesConstRef _key) { Super::remove(sha3(_key)); }

  // empty from the PoV of the iterator interface; still need a basic iterator
  // impl though.
  class iterator {
   public:
    using value_type = std::pair<zbytesConstRef, zbytesConstRef>;

    iterator() {}
    iterator(HashedGenericTrieDB const*) {}
    iterator(HashedGenericTrieDB const*, zbytesConstRef) {}

    iterator& operator++() { return *this; }
    value_type operator*() const { return value_type(); }
    value_type operator->() const { return value_type(); }

    bool operator==(iterator const&) const { return true; }
    bool operator!=(iterator const&) const { return false; }

    value_type at() const { return value_type(); }
  };
  iterator begin() const { return iterator(); }
  iterator end() const { return iterator(); }
  iterator lower_bound(zbytesConstRef) const { return iterator(); }
};

// Hashed & Hash-key mapping
template <class _DB>
class FatGenericTrieDB : private SpecificTrieDB<GenericTrieDB<_DB>, h256> {
  using Super = SpecificTrieDB<GenericTrieDB<_DB>, h256>;

 public:
  using DB = _DB;
  FatGenericTrieDB(DB* _db = nullptr) : Super(_db) {}
  FatGenericTrieDB(DB* _db, h256 _root, Verification _v = Verification::Normal)
      : Super(_db, _root, _v) {}

  using Super::check;
  using Super::db;
  using Super::debugStructure;
  using Super::init;
  using Super::isEmpty;
  using Super::isNull;
  using Super::leftOvers;
  using Super::open;
  using Super::root;
  using Super::setRoot;

  std::string at(zbytesConstRef _key) const { return Super::at(sha3(_key)); }
  bool contains(zbytesConstRef _key) const {
    return Super::contains(sha3(_key));
  }
  void insert(zbytesConstRef _key, zbytesConstRef _value) {
    h256 hash = sha3(_key);
    //            LOG_GENERAL(INFO, "Inserting to FatGenericTrieDB Hash : Value
    //            = " << hash << " : " << _value);
    Super::insert(hash, _value);
    Super::db()->insertAux(hash, _key);
  }

  void remove(zbytesConstRef _key) { Super::remove(sha3(_key)); }

  // iterates over <key, value> pairs
  class iterator : public GenericTrieDB<_DB>::iterator {
   public:
    using Super = typename GenericTrieDB<_DB>::iterator;

    iterator() {}
    iterator(FatGenericTrieDB const* _trie) : Super(_trie) {}

    typename Super::value_type at() const {
      auto hashed = Super::at();
      m_key = static_cast<FatGenericTrieDB const*>(Super::m_that)
                  ->db()
                  ->lookupAux(h256(hashed.first));
      return std::make_pair(&m_key, std::move(hashed.second));
    }

   private:
    mutable zbytes m_key;
  };

  iterator begin() const { return iterator(); }
  iterator end() const { return iterator(); }

  // iterates over <hashedKey, value> pairs
  class HashedIterator : public GenericTrieDB<_DB>::iterator {
   public:
    using Super = typename GenericTrieDB<_DB>::iterator;

    HashedIterator() {}
    HashedIterator(FatGenericTrieDB const* _trie) : Super(_trie) {}

    zbytes key() const {
      auto hashed = Super::at();
      return static_cast<FatGenericTrieDB const*>(Super::m_that)
          ->db()
          ->lookupAux(h256(hashed.first));
    }
  };

  HashedIterator hashedBegin() const { return HashedIterator(this); }
  HashedIterator hashedEnd() const { return HashedIterator(); }
};

template <class KeyType, class DB>
using TrieDB = SpecificTrieDB<GenericTrieDB<DB>, KeyType>;

}  // namespace dev

// Template implementations...
namespace dev {

template <class DB>
GenericTrieDB<DB>::iterator::iterator(GenericTrieDB const* _db) {
  m_that = _db;
  m_trail.push_back({_db->node(_db->m_root), std::string(1, '\0'),
                     255});  // one null byte is the HPE for the empty key.
  next();
}

template <class DB>
GenericTrieDB<DB>::iterator::iterator(GenericTrieDB const* _db,
                                      zbytesConstRef _fullKey) {
  m_that = _db;
  m_trail.push_back({_db->node(_db->m_root), std::string(1, '\0'),
                     255});  // one null byte is the HPE for the empty key.
  next(_fullKey);
}

template <class DB>
typename GenericTrieDB<DB>::iterator::value_type
GenericTrieDB<DB>::iterator::at() const {
  ZIL_FATAL_ASSERT(!m_trail.empty());

  Node const& b = m_trail.back();
  ZIL_FATAL_ASSERT(!b.key.empty());
  ZIL_FATAL_ASSERT((b.key[0] & 0x10) == 0);

  RLP rlp(b.rlp);
  return std::make_pair(zbytesConstRef(b.key).cropped(1),
                        rlp[rlp.itemCount() == 2 ? 1 : 16].payload());
}

template <class DB>
void GenericTrieDB<DB>::iterator::next(NibbleSlice _key) {
  NibbleSlice k = _key;
  while (true) {
    if (m_trail.empty()) {
      m_that = nullptr;
      return;
    }

    Node const& b = m_trail.back();
    RLP rlp(b.rlp);

    if (m_trail.back().child == 255) {
      // Entering. Look for first...
      if (rlp.isEmpty()) {
        // Kill our search as soon as we hit an empty node.
        k.clear();
        m_trail.pop_back();
        continue;
      }
      if (!rlp.isList() || (rlp.itemCount() != 2 && rlp.itemCount() != 17)) {
        m_that = nullptr;
        return;
      }
      if (rlp.itemCount() == 2) {
        // Just turn it into a valid Branch
        auto keyOfRLP = keyOf(rlp);

        // TODO: do something different depending on how keyOfRLP compares to
        // k.mid(0, std::min(k.size(), keyOfRLP.size())); if == all is good -
        // continue descent. if > discard key and continue descent. if < discard
        // key and skip node.

        if (!k.contains(keyOfRLP)) {
          if (!k.isEarlierThan(keyOfRLP)) {
            k.clear();
            m_trail.pop_back();
            continue;
          }
          k.clear();
        }

        k = k.mid(std::min(k.size(), keyOfRLP.size()));
        m_trail.back().key =
            hexPrefixEncode(keyOf(m_trail.back().key), keyOfRLP, false);
        if (isLeaf(rlp)) {
          // leaf - exit now.
          if (k.empty()) {
            m_trail.back().child = 0;
            return;
          }
          // Still data in key we're supposed to be looking for when we're at a
          // leaf. Go for next one.
          k.clear();
          m_trail.pop_back();
          continue;
        }

        // enter child.
        m_trail.back().rlp = m_that->deref(rlp[1]);
        // no need to set .child as 255 - it's already done.
        continue;
      } else {
        // Already a branch - look for first valid.
        if (k.size()) {
          m_trail.back().setChild(k[0]);
          k = k.mid(1);
        } else {
          m_trail.back().setChild(16);
        }
        // run through to...
      }
    } else {
      // Continuing/exiting. Look for next...
      if (!(rlp.isList() && rlp.itemCount() == 17)) {
        k.clear();
        m_trail.pop_back();
        continue;
      }
      // else run through to...
      m_trail.back().incrementChild();
    }

    // ...here. should only get here if we're a list.
    ZIL_FATAL_ASSERT(rlp.isList() && rlp.itemCount() == 17);

    for (;; m_trail.back().incrementChild()) {
      if (m_trail.back().child == 17) {
        // finished here.
        k.clear();
        m_trail.pop_back();
        break;
      } else if (!rlp[m_trail.back().child].isEmpty()) {
        if (m_trail.back().child == 16) {
          return;  // have a value at this node - exit now.
        } else {
          // lead-on to another node - enter child.
          // fixed so that Node passed into push_back is constructed *before*
          // m_trail is potentially resized (which invalidates back and rlp)
          Node const& back = m_trail.back();
          m_trail.push_back(Node{
              m_that->deref(rlp[back.child]),
              hexPrefixEncode(keyOf(back.key),
                              NibbleSlice(zbytesConstRef(&back.child, 1), 1),
                              false),
              255});
          break;
        }
      } else {
        k.clear();
      }
    }
  }
}

template <class DB>
void GenericTrieDB<DB>::iterator::next() {
  while (true) {
    if (m_trail.empty()) {
      m_that = nullptr;
      return;
    }

    Node const& b = m_trail.back();
    RLP rlp(b.rlp);

    if (m_trail.back().child == 255) {
      // Entering. Look for first...
      if (rlp.isEmpty()) {
        m_trail.pop_back();
        continue;
      }
      if (!(rlp.isList() && (rlp.itemCount() == 2 || rlp.itemCount() == 17))) {
        m_that = nullptr;
        return;
      }
      if (rlp.itemCount() == 2) {
        // Just turn it into a valid Branch
        m_trail.back().key =
            hexPrefixEncode(keyOf(m_trail.back().key), keyOf(rlp), false);
        if (isLeaf(rlp)) {
          // leaf - exit now.
          m_trail.back().child = 0;
          return;
        }

        // enter child.
        m_trail.back().rlp = m_that->deref(rlp[1]);
        // no need to set .child as 255 - it's already done.
        continue;
      } else {
        // Already a branch - look for first valid.
        m_trail.back().setFirstChild();
        // run through to...
      }
    } else {
      // Continuing/exiting. Look for next...
      if (!(rlp.isList() && rlp.itemCount() == 17)) {
        m_trail.pop_back();
        continue;
      }
      // else run through to...
      m_trail.back().incrementChild();
    }

    // ...here. should only get here if we're a list.
    ZIL_FATAL_ASSERT(rlp.isList() && rlp.itemCount() == 17);

    for (;; m_trail.back().incrementChild()) {
      if (m_trail.back().child == 17) {
        // finished here.
        m_trail.pop_back();
        break;
      } else if (!rlp[m_trail.back().child].isEmpty()) {
        if (m_trail.back().child == 16) {
          return;  // have a value at this node - exit now.
        } else {
          // lead-on to another node - enter child.
          // fixed so that Node passed into push_back is constructed *before*
          // m_trail is potentially resized (which invalidates back and rlp)
          Node const& back = m_trail.back();
          m_trail.push_back(Node{
              m_that->deref(rlp[back.child]),
              hexPrefixEncode(keyOf(back.key),
                              NibbleSlice(zbytesConstRef(&back.child, 1), 1),
                              false),
              255});
          break;
        }
      }
    }
  }
}

template <class KeyType, class DB>
typename SpecificTrieDB<KeyType, DB>::iterator::value_type
SpecificTrieDB<KeyType, DB>::iterator::at() const {
  auto p = Super::at();
  value_type ret;

  ZIL_FATAL_ASSERT(p.first.size() == sizeof(KeyType));

  memcpy(&ret.first, p.first.data(), sizeof(KeyType));
  ret.second = p.second;
  return ret;
}

template <class DB>
void GenericTrieDB<DB>::insert(zbytesConstRef _key, zbytesConstRef _value) {
  //        LOG_GENERAL(INFO, "Inserting to GenericTrieDB Key : Value = " <<
  //        _key << " : " << _value);
  std::string rootValue = node(m_root);

  ZIL_FATAL_ASSERT(!rootValue.empty());

  zbytes b = mergeAt(RLP(rootValue), m_root, NibbleSlice(_key), _value);

  // mergeAt won't attempt to delete the node if it's less than 32 bytes
  // However, we know it's the root node and thus always hashed.
  // So, if it's less than 32 (and thus should have been deleted but wasn't)
  // then we delete it here.
  if (rootValue.size() < 32) forceKillNode(m_root);
  m_root = forceInsertNode(&b);
}

template <class DB>
std::string GenericTrieDB<DB>::at(zbytesConstRef _key) const {
  return atAux(RLP(node(m_root)), _key);
}

template <class DB>
std::string GenericTrieDB<DB>::atAux(RLP const& _here, NibbleSlice _key) const {
  if (_here.isEmpty() || _here.isNull())
    // not found.
    return std::string();
  unsigned itemCount = _here.itemCount();

  ZIL_FATAL_ASSERT(_here.isList() && !(itemCount != 2 && itemCount != 17));

  if (itemCount == 2) {
    auto k = keyOf(_here);
    if (_key == k && isLeaf(_here))
      // reached leaf and it's us
      return _here[1].toString();
    else if (_key.contains(k) && !isLeaf(_here))
      // not yet at leaf and it might yet be us. onwards...
      return atAux(
          _here[1].isList() ? _here[1] : RLP(node(_here[1].toHash<h256>())),
          _key.mid(k.size()));
    else
      // not us.
      return std::string();
  } else {
    if (_key.size() == 0) return _here[16].toString();
    auto n = _here[_key[0]];
    if (n.isEmpty())
      return std::string();
    else
      return atAux(n.isList() ? n : RLP(node(n.toHash<h256>())), _key.mid(1));
  }
}

template <class DB>
std::string GenericTrieDB<DB>::getProof(zbytesConstRef _key,
                                        std::set<std::string>& nodes) const {
  LOG_MARKER();
  return getProof(RLP(node(m_root)), _key, nodes);
}

template <class DB>
std::string GenericTrieDB<DB>::getProof(RLP const& _here, NibbleSlice _key,
                                        std::set<std::string>& nodes) const {
  LOG_MARKER();
  if (_here.isEmpty() || _here.isNull()) {
    // not found.
    return std::string();
  }
  unsigned itemCount = _here.itemCount();

  ZIL_FATAL_ASSERT(_here.isList() && !(itemCount != 2 && itemCount != 17));

  if (itemCount == 2) {
    nodes.emplace(_here.data().toString());
    auto k = keyOf(_here);
    if (_key == k && isLeaf(_here)) {
      // reached leaf and it's us
      return _here[1].toString();
    } else if (_key.contains(k) && !isLeaf(_here)) {
      // not yet at leaf and it might yet be us. onwards...
      return getProof(
          _here[1].isList() ? _here[1] : RLP(node(_here[1].toHash<h256>())),
          _key.mid(k.size()), nodes);
    } else {
      // not us.
      return std::string();
    }
  } else {
    // nodes.emplace(sha3(_here.data()), _here.data().toBytes());
    nodes.emplace(_here.data().toString());
    if (_key.size() == 0) {
      return getProof(_here[16], _key, nodes);
    }
    auto n = _here[_key[0]];
    if (n.isEmpty()) {
      return std::string();
    } else {
      return getProof(n.isList() ? n : RLP(node(n.toHash<h256>())), _key.mid(1),
                      nodes);
    }
  }
}

template <class DB>
zbytes GenericTrieDB<DB>::mergeAt(RLP const& _orig, NibbleSlice _k,
                                  zbytesConstRef _v, bool _inLine) {
  return mergeAt(_orig, sha3(_orig.data()), _k, _v, _inLine);
}

template <class DB>
zbytes GenericTrieDB<DB>::mergeAt(RLP const& _orig, h256 const& _origHash,
                                  NibbleSlice _k, zbytesConstRef _v,
                                  bool _inLine) {
  // The caller will make sure that the bytes are inserted properly.
  // - This might mean inserting an entry into m_over
  // We will take care to ensure that (our reference to) _orig is killed.

  // Empty - just insert here
  if (_orig.isEmpty()) return place(_orig, _k, _v);

  unsigned itemCount = _orig.itemCount();

  ZIL_FATAL_ASSERT(_orig.isList() && !(itemCount != 2 && itemCount != 17));

  if (itemCount == 2) {
    // pair...
    NibbleSlice k = keyOf(_orig);

    // exactly our node - place value in directly.
    if (k == _k && isLeaf(_orig)) return place(_orig, _k, _v);

    // partial key is our key - move down.
    if (_k.contains(k) && !isLeaf(_orig)) {
      if (!_inLine) killNode(_orig, _origHash);
      RLPStream s(2);
      s.append(_orig[0]);
      mergeAtAux(s, _orig[1], _k.mid(k.size()), _v);
      return s.out();
    }

    auto sh = _k.shared(k);
    //		std::cout << _k << " sh " << k << " = " << sh << std::endl;
    if (sh) {
      // shared stuff - cleve at disagreement.
      auto cleved = cleve(_orig, sh);
      return mergeAt(RLP(cleved), _k, _v, true);
    } else {
      // nothing shared - branch
      auto branched = branch(_orig);
      return mergeAt(RLP(branched), _k, _v, true);
    }
  } else {
    // branch...

    // exactly our node - place value.
    if (_k.size() == 0) return place(_orig, _k, _v);

    // Kill the node.
    if (!_inLine) killNode(_orig, _origHash);

    // not exactly our node - delve to next level at the correct index.
    zbyte n = _k[0];
    RLPStream r(17);
    for (zbyte i = 0; i < 17; ++i)
      if (i == n)
        mergeAtAux(r, _orig[i], _k.mid(1), _v);
      else
        r.append(_orig[i]);
    return r.out();
  }
}

template <class DB>
void GenericTrieDB<DB>::mergeAtAux(RLPStream& _out, RLP const& _orig,
                                   NibbleSlice _k, zbytesConstRef _v) {
  RLP r = _orig;
  std::string s;
  // _orig is always a segment of a node's RLP - removing it alone is pointless.
  // However, if may be a hash, in which case we deref and we know it is
  // removable.
  bool isRemovable = false;
  if (!r.isList() && !r.isEmpty()) {
    s = node(_orig.toHash<h256>());
    r = RLP(s);

    ZIL_FATAL_ASSERT(!r.isNull());

    isRemovable = true;
  }
  zbytes b = mergeAt(r, _k, _v, !isRemovable);
  streamNode(_out, b);
}

template <class DB>
void GenericTrieDB<DB>::remove(zbytesConstRef _key) {
  std::string rv = node(m_root);
  zbytes b = deleteAt(RLP(rv), NibbleSlice(_key));
  if (b.size()) {
    if (rv.size() < 32) forceKillNode(m_root);
    m_root = forceInsertNode(&b);
  }
}

template <class DB>
bool GenericTrieDB<DB>::isTwoItemNode(RLP const& _n) const {
  return (_n.isData() && RLP(node(_n.toHash<h256>())).itemCount() == 2) ||
         (_n.isList() && _n.itemCount() == 2);
}

template <class DB>
std::string GenericTrieDB<DB>::deref(RLP const& _n) const {
  LOG_MARKER();
  return _n.isList() ? _n.data().toString() : node(_n.toHash<h256>());
}

template <class DB>
zbytes GenericTrieDB<DB>::deleteAt(RLP const& _orig, NibbleSlice _k) {
  // The caller will make sure that the bytes are inserted properly.
  // - This might mean inserting an entry into m_over
  // We will take care to ensure that (our reference to) _orig is killed.

  // Empty - not found - no change.
  if (_orig.isEmpty()) return zbytes();

  ZIL_FATAL_ASSERT(_orig.isList() && !(_orig.itemCount() != 2 && _orig.itemCount() != 17));

  if (_orig.itemCount() == 2) {
    // pair...
    NibbleSlice k = keyOf(_orig);

    // exactly our node - return null.
    if (k == _k && isLeaf(_orig)) {
      killNode(_orig);
      return RLPNull;
    }

    // partial key is our key - move down.
    if (_k.contains(k)) {
      RLPStream s;
      s.appendList(2) << _orig[0];
      if (!deleteAtAux(s, _orig[1], _k.mid(k.size()))) return zbytes();
      killNode(_orig);
      RLP r(s.out());
      if (isTwoItemNode(r[1])) return graft(r);
      return s.out();
    } else
      // not found - no change.
      return zbytes();
  } else {
    // branch...

    // exactly our node - remove and rejig.
    if (_k.size() == 0 && !_orig[16].isEmpty()) {
      // Kill the node.
      killNode(_orig);

      zbyte used = uniqueInUse(_orig, 16);
      if (used != 255)
        if (isTwoItemNode(_orig[used])) {
          auto merged = merge(_orig, used);
          return graft(RLP(merged));
        } else
          return merge(_orig, used);
      else {
        RLPStream r(17);
        for (zbyte i = 0; i < 16; ++i) r << _orig[i];
        r << "";
        return r.out();
      }
    } else {
      // not exactly our node - delve to next level at the correct index.
      RLPStream r(17);
      zbyte n = _k[0];
      for (zbyte i = 0; i < 17; ++i)
        if (i == n)
          if (!deleteAtAux(r, _orig[i],
                           _k.mid(1)))  // bomb out if the key didn't turn up.
            return zbytes();
          else {
          }
        else
          r << _orig[i];

      // Kill the node.
      killNode(_orig);

      // check if we ended up leaving the node invalid.
      RLP rlp(r.out());
      zbyte used = uniqueInUse(rlp, 255);
      if (used == 255)  // no - all ok.
        return r.out();

      // yes; merge
      if (isTwoItemNode(rlp[used])) {
        auto merged = merge(rlp, used);
        return graft(RLP(merged));
      } else
        return merge(rlp, used);
    }
  }
}

template <class DB>
bool GenericTrieDB<DB>::deleteAtAux(RLPStream& _out, RLP const& _orig,
                                    NibbleSlice _k) {
  zbytes b =
      _orig.isEmpty()
          ? zbytes()
          : deleteAt(_orig.isList() ? _orig : RLP(node(_orig.toHash<h256>())),
                     _k);

  if (!b.size())  // not found - no change.
    return false;

  /*	if (_orig.isList())
                  killNode(_orig);
          else
                  killNode(_orig.toHash<h256>());*/

  streamNode(_out, b);
  return true;
}

template <class DB>
zbytes GenericTrieDB<DB>::place(RLP const& _orig, NibbleSlice _k,
                                zbytesConstRef _s) {
  killNode(_orig);
  if (_orig.isEmpty()) return rlpList(hexPrefixEncode(_k, true), _s);

  ZIL_FATAL_ASSERT(_orig.isList() && !(_orig.itemCount() != 2 && _orig.itemCount() != 17));

  if (_orig.itemCount() == 2) return rlpList(_orig[0], _s);

  auto s = RLPStream(17);
  for (unsigned i = 0; i < 16; ++i) s << _orig[i];
  s << _s;
  return s.out();
}

// in1: [K, S] (DEL)
// out1: null
// in2: [V0, ..., V15, S] (DEL)
// out2: [V0, ..., V15, null] iff exists i: !!Vi  -- OR --  null otherwise
template <class DB>
zbytes GenericTrieDB<DB>::remove(RLP const& _orig) {
  killNode(_orig);

  ZIL_FATAL_ASSERT(_orig.isList() && !(_orig.itemCount() != 2 && _orig.itemCount() != 17));

  if (_orig.itemCount() == 2) return RLPNull;
  RLPStream r(17);
  for (unsigned i = 0; i < 16; ++i) r << _orig[i];
  r << "";
  return r.out();
}

template <class DB>
RLPStream& GenericTrieDB<DB>::streamNode(RLPStream& _s, zbytes const& _b) {
  if (_b.size() < 32)
    _s.appendRaw(_b);
  else
    _s.append(forceInsertNode(&_b));
  return _s;
}

template <class DB>
zbytes GenericTrieDB<DB>::cleve(RLP const& _orig, unsigned _s) {
  killNode(_orig);

  ZIL_FATAL_ASSERT(_orig.isList() && _orig.itemCount() == 2);

  auto k = keyOf(_orig);

  ZIL_FATAL_ASSERT(_s && _s <= k.size());

  RLPStream bottom(2);
  bottom << hexPrefixEncode(k, isLeaf(_orig), /*ugh*/ (int)_s) << _orig[1];

  RLPStream top(2);
  top << hexPrefixEncode(k, false, 0, /*ugh*/ (int)_s);
  streamNode(top, bottom.out());

  return top.out();
}

template <class DB>
zbytes GenericTrieDB<DB>::graft(RLP const& _orig) {
  ZIL_FATAL_ASSERT(_orig.isList() && _orig.itemCount() == 2);

  std::string s;
  RLP n;
  if (_orig[1].isList())
    n = _orig[1];
  else {
    // remove second item from the trie after derefrencing it into s & n.
    auto lh = _orig[1].toHash<h256>();
    s = node(lh);
    forceKillNode(lh);
    n = RLP(s);
  }

  ZIL_FATAL_ASSERT(n.itemCount() == 2);

  return rlpList(hexPrefixEncode(keyOf(_orig), keyOf(n), isLeaf(n)), n[1]);
  //	auto ret =
  //	std::cout << keyOf(_orig) << " ++ " << keyOf(n) << " == " <<
  // keyOf(RLP(ret)) << std::endl; 	return ret;
}

template <class DB>
zbytes GenericTrieDB<DB>::merge(RLP const& _orig, zbyte _i) {
  ZIL_FATAL_ASSERT(_orig.isList() && _orig.itemCount() == 17);

  RLPStream s(2);
  if (_i != 16) {
    ZIL_FATAL_ASSERT(!_orig[_i].isEmpty());

    s << hexPrefixEncode(zbytesConstRef(&_i, 1), false, 1, 2, 0);
  } else
    s << hexPrefixEncode(zbytes(), true);
  s << _orig[_i];
  return s.out();
}

template <class DB>
zbytes GenericTrieDB<DB>::branch(RLP const& _orig) {
  ZIL_FATAL_ASSERT(_orig.isList() && _orig.itemCount() == 2);

  killNode(_orig);

  auto k = keyOf(_orig);
  RLPStream r(17);
  if (k.size() == 0) {
    ZIL_FATAL_ASSERT(isLeaf(_orig));

    for (unsigned i = 0; i < 16; ++i) r << "";
    r << _orig[1];
  } else {
    zbyte b = k[0];
    for (unsigned i = 0; i < 16; ++i)
      if (i == b)
        if (isLeaf(_orig) || k.size() > 1)
          streamNode(
              r, rlpList(hexPrefixEncode(k.mid(1), isLeaf(_orig)), _orig[1]));
        else
          r << _orig[1];
      else
        r << "";
    r << "";
  }
  return r.out();
}
}  // namespace dev

#endif  // __TRIEDB_H__
